A complex object is an instance of a data type or object-oriented class that contains zero or more scalar attributes (e.g. integers, characters, etc.) and one or more attributes that can point to or reference other complex objects. An attribute capable of pointing to or referencing another object is referred to herein as a "pointer." Thus, a complex object may be mapped to a top-level data structure with one or more pointers to other data structures that in turn may have pointers to other data structures. Examples of complex objects include linked lists, trees, and graphs.
Memory to store complex objects is typically dynamically allocated from an area of memory available to a program called a "heap." More specifically, each data structure in the complex object, including the complex objects to which the complex object has pointers, is individually allocated from the heap and referenced by a pointer. Thus, a top-level data structure of a complex object includes pointers to secondarily allocated data structures. The dynamic memory allocation for a complex may be performed by a vendor-supplied operating system or run-time library call, such as malloc(3) on Unix operating system platforms, or by a user-supplied memory allocation routine that ultimately makes an independent call to a vendor-supplied memory allocation routine. This type of memory allocation typically results in the dispersion of a complex object over many non-contiguous areas of the heap, due to piecemeal allocation of the complex object and heap fragmentation after many allocations and deallocations.
For example, in FIG. 6, complex object p is created in step 600 by making n calls to a dynamic memory allocation routine called "alloc." Complex object p uses five non-contiguous areas of memory in heap 610, labeled p.sub.1, p.sub.2, p.sub.3, p.sub.4, and p.sub.5, respectively. In addition, another complex object q is created in step 602, consuming four non-contiguous areas of memory in the heap, labeled q.sub.1, q.sub.2, q.sub.3, and q.sub.4. Heap 612 illustrates the heap 610 after memory has been allocated for complex object q.
When a complex object is no longer needed by the program, the individually allocated data structures of the complex object are deallocated or "freed" to allow the memory currently being used to store the complex object to be recycled (i.e. to be made available for other purposes). Thus, freeing a complex object involves freeing each allocated data structure belonging to the complex object. Deallocation of a complex object typically involves traversing the structure of the complex object by following pointers stored in the various data structures that make up the complex object. These pointers are followed to locate and deallocate the various non-contiguous areas of the heap used to store the data structures belonging to the complex parameter.
Since traversing a complex data structure is type-dependent, a deallocation routine is written for each complex object type. Referring again to FIG. 6, the complex object p is deallocated in step 604 by calling a type-specific deallocation routine called "P_free( )" with the complex object p passed in as a parameter. In response, the complex object p is traversed and each of the dynamically allocated memory areas that belong to p is freed by a separate call to free(p.sub.n). Heap 614 illustrates the state of heap 612 after memory for p is no longer allocated. Likewise, complex object q is deallocated by calling a different "Q_free( )" routine in step 606. The "Q_free( )" routine traverses the data structures of complex object q and frees the individually allocated memory areas of the complex object with individual calls to free(q.sub.n). Heap 616 illustrates heap 614 after complex object q has been deallocated. Therefore, this "per-object" deallocation approach can be computationally expensive, and the computational cost for performing deallocation for a complex object increases with the complexity of the object.
A "per-client" memory management approach that may reduce the computational expense in deallocating complex objects is available in the Distributed Computing Environment (DCE) defined by the Open Software Foundation (OSF). According to this approach, an application programmer codes the following function call before a call to one or more client stub routines that return complex objects: EQU rpc_ss_set_client_alloc_free(rpc_ss_allocate, rpc_ss_free);
When called, this routine instantiates a new dynamic memory management system for the process and registers new memory allocation and deallocation routines. When the called client stub routines return complex objects, the client stub routines invoke the registered memory allocation routine, rpc_ss_allocate, to dynamically allocate memory for the complex objects within the new memory management system. When all of the complex objects are no longer needed outside the client stub routines that created them, the entire new memory management system may be torn down, releasing all the memory allocated for the complex objects. This process may be coded by an application program with a rpc_ss_disable_allocate( ) function call.
Referring the FIG. 7, an application programmer instantiates a new memory management system with a call to the enable routine in step 700, which registers an appropriate memory allocation routine for the new memory management system and sets up an area 720 in heap 710 for allocating memory. In step 702, when complex object p is instantiated, memory for complex object p is allocated by the registered memory allocation routine from memory area 720 as shown in heap 712. When complex object q is created in step 704, memory for complex object q is also allocated from memory area 720 as shown in heap 714. Finally, after both complex object p and complex object q are no longer needed, the application programmer disables the new memory management system in step 706 by coding an appropriate disable call, thereby releasing the memory for all the allocated memory, including complex objects p and q. Heap 716 depicts heap 714 after the disable call routine is executed.
Although the process of tearing down the memory management system to release the memory for all the allocated complex objects can be less computationally expensive than the "per-object" deallocation approach, the "per-client" approach is less flexible because different complex objects typically have different and overlapping lifetimes. The lifetime of a complex object is the period from the creation of the complex object until the last use of the complex object. For example, referring back to FIG. 7, the lifetime 732 of complex object q commences at step 704 and ends when it is no longer needs at step 706, where it can be safely deallocated. In this example, the lifetime 730 of complex object p commences at step 702, extends beyond the creation of complex object q in step 704, and ends some time before the end of the lifetime 732 of complex object q. Consequently, the lifetime 730 of complex object p overlaps the lifetime 732 of complex object q because complex object q was created after complex object p was created but before complex object p was terminated.
In this situation, the "per-client" memory management system cannot be taken down at the end of the lifetime 730 of complex object p because deallocation of memory area 720 will prematurely release the allocated memory for complex object q. In contrast, the "per-object" deallocation allows the complex object to be freed at the end of its lifetime. Referring again to FIG. 6, complex object p is freed in step 604 at the end of its lifetime 620, and complex object q is freed in step 606 at the end of its lifetime 622.
One conventional attempt to handle overlapping lifetimes is convert a complex object from a "per-client" memory management approach to a "per-object" memory management approach. Accordingly, the complex object is cloned from the "per-client" memory management area into a more persistent area of the heap by performing a deep copy operation on the complex object. A deep copy, however, is a computationally expensive operation because the complex object data structure needs to be traversed to visit every node in the complex object for copying. Furthermore, freeing the cloned complex object requires the expensive traversal of the complex object as in the "per-object" approach. Consequently, the conscientious application programmer is faced with a dilemma: either to defer the deallocation of the memory for complex object p, thereby wasting memory resources, or to deallocate complex object p according to the "per-object" approach and incur the computational overhead of traversing the data structures and pointers of complex object p.
Another problem with the "per-client" approach is that it is error-prone. There are several operations an application programmer must code for every procedure call that returns complex objects, and it is easy to overlook or miscode one of the operations, resulting in a bug that causes the program to malfunction. For example, the application programmer may instantiate a new memory management system without realizing that another memory management system is in effect, thereby causing the previously allocated memory to be lost. Memory allocation errors are usually very subtle and are some of the most difficult bugs to diagnose and fix.
Therefore, there is a need for a memory management system and methodology that avoids the computational costs in traversing complex objects present in the conventional "per-object" deallocation approach while avoiding the loss of flexibility incurred by using the "per-client" deallocation approach. There is also a need for reducing bugs in implementing a memory management system.